package com.aug_leo.datastructure.linkedlist;

/**
 * 查找链表中间节点
 */
public class E08Leetcode876 {

    /*
                p1
                        p2
        1   2   3   4   5   null


                    p1
                                p2
        1   2   3   4   5   6   null
     */

    /**
     * <h3>快慢指针</h3>
     * 快指针一次走两步，慢指针一次走一步，当快指针到链表结尾时，慢指针恰好走到链表的一半
     * 返回链表的中间节点
     * 通过使用两个指针，一个每次移动一步，另一个每次移动两步，当移动两步的指针到达链表末尾时，移动一步的指针正好指向链表的中间节点
     * 这种方法适用于未知长度的链表，且无需遍历整个链表
     *
     * @param head 链表的头节点
     * @return 链表的中间节点
     */
    public ListNode middleNode(ListNode head) {
        // 初始化两个指针，都指向链表的头结点
        ListNode pointer1 = head; // 慢指针，中间点
        ListNode pointer2 = head; // 快指针
        // 当移动两步的指针未到达链表末尾时，继续移动
        while (pointer2 != null && pointer2.next != null) {
            // 移动一步的指针前进一步
            pointer1 = pointer1.next;
            // 移动两步的指针前进两步
            pointer2 = pointer2.next.next;
        }
        // 返回移动一步的指针，即链表的中间节点
        return pointer1;
    }

    public static void main(String[] args) {
        ListNode head1 = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(new E08Leetcode876().middleNode(head1));

        ListNode head2 = ListNode.of(1, 2, 3, 4, 5, 6);
        System.out.println(new E08Leetcode876().middleNode(head2));
    }
}
